package cn.dlc.com.priorityqueue;

import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/26 7:03
 * @desc 最小优先队列
 */
@Data
public class MinPriorityQueue<T extends Comparable<T>> {

    private T[] items;
    private int num;

    public MinPriorityQueue(int capacity){
        this.items = (T[]) new Comparable[capacity + 1];
        this.num = 0;
    }

    public int size(){
        return num;
    }

    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    public boolean isEmpty(){
        return this.num == 0;
    }

    // 删除最小元素
    public T delMax(){
        // 记录最大的值
        T temp = items[1];

        // 交换最后一个元素和1处的元素
        exchange(1,num);
        // 最后一个元素不再进入排序
        this.num--;
        // 下沉
        sink(1);
        // 返回最大值
        return temp;
    }

    // 下沉
    private void sink(int k) {

        while(2*k <= this.num) {

            // 记录最小索引
            int min;

            // 有右子节点的话，继续循环
            if(2*k + 1 <= this.num) {
                // 有右子结点
                if(less(2*k, 2*k+1)) {
                    // 右子结点更加小
                    min = 2*k;
                } else {
                    min = 2*k + 1;
                }
            } else {
                min = 2*k;
            }
            // 比较max和当前节点的大小
            if(less(k, min)) {
                // 当前节点更小,不需要继续
                break;
            }
            // 否则交换位置,并列更换指向重新循环
            exchange(min,k);
            k = min;
        }
    }

    public void insert(T t) {
        items[++num] = t;
        swim(num);
    }
    // 上浮
    private void swim(int k) {

        // 非根节点的位置，继续循环
        while(k > 1) {
            if(less(k, k / 2)) {
                // 插入的节点小一些，交换
                exchange(k, k / 2);
            } else {
                // 父节点更小
                break;
            }

            // 重置k的值
            k = k / 2;
        }
    }
}
